package Stack;

/**
 *  题目 ：无法吃午饭的学生数量
 *  题目详述 ：
 *  学校的自助午餐提供圆形和方形的三明治，分别用数字0和1表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
 * 餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个栈里，每一轮：
 *
 * 如果队列最前面的学生喜欢栈顶的三明治，那么会拿走它并离开队列。
 * 否则，这名学生会放弃这个三明治并回到队列的尾部。
 * 这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
 *
 * 给你两个整数数组students 和sandwiches，其中sandwiches[i]是栈里面第i个三明治的类型
 * （i = 0是栈的顶部），students[j]是初始队列里第j名学生对三明治的喜好（j = 0是队列的最开始位置）。
 * 请你返回无法吃午餐的学生数量。
 *
 */
public class P1700 {
    /**
     * 核心思想 ：（使用数组实现，由于其所给的是数组形式，使用的是 栈和队列 的思想）
     * 即，在取栈顶元素（三明治）时，要去判断学生队列中是否已经不存在与栈顶元素一致的数量是否为零
     * @param students
     * @param sandwiches
     * @return
     */
    public int countStudents(int[] students, int[] sandwiches) {
        int s0 = 0, s1 = 0;
        // s0,代表喜欢圆形三明治的学生数量；
        // s1，代表喜欢方形三明治的学生数量；
        for(int i = 0 ;i < students.length ; i++){
            // 遍历整个学生数组，获取s0，s1的值
            // 时间复杂度为 ：O（n）
            if(students[i] == 0){
                s0++;
            }
            else {
                s1++;
            }
        }
        for(int i = 0 ; i < sandwiches.length ; i++){
            // 遍历整个sandwiches数组，即，相当于获取三明治栈顶元素，将其与各自喜欢不同样式三名字的学生数量进行对比
            if(sandwiches[i] == 0 && s0 > 0 ){
                // 即，当三明治为圆形（值为0），同时喜欢圆形三明治的学生数量大于0
                s0--;
                continue; // 需要继续遍历下一个三明治（即，相当于将栈中的上一个元素弹出，同时继续比较下一个栈顶元素）
            }
            else if(sandwiches[i] == 1 && s1 > 0){
                s1--;
                continue;
            }
            else {
                // 若是栈顶元元素不符合以上任何条件，即，后续的都不能满足，直接退出循环即可
                break;
            }
        }
        return s0 + s1;
        // 返回一开始统计的喜欢不同类型三明治的学生数目
    }
}
